//
// Created by Administrator on 2021/4/8.
//
/*给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
}
        填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有next 指针都被设置为 NULL。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <queue>
#include <iostream>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}

    explicit Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
            : val(_val), left(_left), right(_right), next(_next) {}
};


class Solution {
public:
    Node *connect(Node *root) {
        // 类似层次遍历?
        if (root == nullptr) return root;
        queue<Node *> q;  // 构造一个队列
        q.push(root);
        while (not q.empty()) {
            int n = (int) q.size();
            for (int i = 0; i <= n - 1; i++) {
                Node *node = q.front();
                q.pop();
                if (i < n - 1) // 不是这一层的最后一个，都可以指向队首，即下一个右侧节点
                    node->next = q.front(); // 指向右侧
                if (node->left != nullptr) {
                    q.push(node->left); // 左子节点入队
                    q.push(node->right); // 右子节点入队
                }
            }
        }
        return root;
    }

    vector<vector<int>> levelOrder(Node *root) { //  层次遍历
        vector<vector<int>> ret;
        if (!root) {
            return ret;
        }
        queue<Node *> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = (int) q.size();
            ret.emplace_back();
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front();
                q.pop();
                ret.back().push_back(node->val);
                if (node->next == nullptr) {
                    ret.back().push_back(1998); // 1998代替#
                }
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ret;
    }
};

class Solution2 { // 题解
public:
    Node *connect(Node *root) {
        if (root == nullptr) {
            return root;
        }

        // 初始化队列同时将第一层节点加入队列中，即根节点
        queue<Node *> Q;
        Q.push(root);

        // 外层的 while 循环迭代的是层数
        while (!Q.empty()) {

            // 记录当前队列大小
            int size = Q.size();

            // 遍历这一层的所有节点
            for (int i = 0; i < size; i++) {

                // 从队首取出元素
                Node *node = Q.front();
                Q.pop();

                // 连接
                if (i < size - 1) {
                    node->next = Q.front();
                }

                // 拓展下一层节点
                if (node->left != nullptr) {
                    Q.push(node->left);
                }
                if (node->right != nullptr) {
                    Q.push(node->right);
                }
            }
        }

        // 返回根节点
        return root;
    }
};

class Solution3 {  // 题解 利用已经建立的next指针 链表式搜索
public:
    Node *connect(Node *root) {
        if (root == nullptr) {
            return root;
        }
        // 从根节点开始
        Node *leftmost = root;
        while (leftmost->left != nullptr) {
            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node *head = leftmost;
            while (head != nullptr) {
                // CONNECTION 1    同一个父节点的连接
                head->left->next = head->right;
                // CONNECTION 2   两个父节点间的连接
                if (head->next != nullptr) {
                    head->right->next = head->next->left;
                }
                // 指针向后移动
                head = head->next;
            }
            // 去下一层的最左的节点
            leftmost = leftmost->left;
        }
        return root;
    }
};


int main() {
//    输入：root = [1,2,3,4,5,6,7]
//    输出：[1,#,2,3,#,4,5,6,7,#]
    auto t7 = Node(7);
    auto t6 = Node(6);
    auto t5 = Node(5);
    auto t4 = Node(4);
    auto t3 = Node(3, &t6, &t7, nullptr);
    auto t2 = Node(2, &t4, &t5, nullptr);
    auto t1 = Node(1, &t2, &t3, nullptr);
    Solution sol;
    sol.connect(&t1);
    vector<vector<int>> ans = sol.levelOrder(&t1);
    for (auto &an : ans) {
        for (int j : an) {
            cout << j << endl;
        }
    }
}